/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        /*
        将所有节点及空子节点放入result之后，再将result之后的多余的null删除;
        使用队列实现逐行从左到右遍历二叉树;
        to_string(),stoi()分别是将其他类型转换为string、int类型的函数
        */
        if(!root)  return "[null]";
        queue<TreeNode*> q;
        string result = "[";
        q.push(root);
        while(!q.empty()){
            if(q.front()){
                result = result + to_string(q.front()->val) + ',';
                q.push(q.front()->left);
                q.push(q.front()->right);
            }else{
                result += "null,";
            }
            q.pop();
        }

        int endOfResult = result.size() - 1;
        while(result[endOfResult] < '0' || result[endOfResult] > '9'){
            result.pop_back();
            --endOfResult;
        }
        result += ']';

        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "[null]")  return NULL;
        /*
        将字符串里的各个节点值转换为int并重建树节点，将重建后的节点存入指针数组中；
        通过序列指针数组来重构二叉树;
        创建一寻找子节点指针，可清楚指明剩余节点中哪些已被设置为子节点：
        (使得寻找子节点时间复杂度降为O(n),且不必单独为每个节点设置布尔数组来标示是否被选为子节点)
        */
        int dataptr = 0;  //字符串下标
        while(data[dataptr] == ' ')  ++dataptr;

        if(data[dataptr] == '[')  ++dataptr;

        vector<TreeNode*> dataToTree;
        int sizeOfData = data.size();
        while(dataptr < sizeOfData && data[dataptr] != ']'){
            string temp = "";  //读取的每个结点值
            while(dataptr < sizeOfData && data[dataptr] != ','){
                temp += data[dataptr];
                ++dataptr;
            }

            if(temp == "null"){
                dataToTree.push_back(NULL);
            }else{
                TreeNode* pTreeNode = new TreeNode(stoi(temp));
                dataToTree.push_back(pTreeNode);
            }
            ++dataptr;
        }

        //重构二叉树
        int endOfDataToTree = dataToTree.size();
        int dataToTreeptr = 0;
        int findTree = dataToTreeptr + 1;//寻找左子树下标
        while(dataToTreeptr < endOfDataToTree && findTree < endOfDataToTree){
            if(findTree <= dataToTreeptr)  break;
            if(!dataToTree[dataToTreeptr]){
                ++dataToTreeptr;
                continue;
            }

            //设定该节点的左右子树
            dataToTree[dataToTreeptr]->left = dataToTree[findTree];
            ++findTree;
            if(findTree < endOfDataToTree){
                dataToTree[dataToTreeptr]->right = dataToTree[findTree];
                ++findTree;
            }
            ++dataToTreeptr;
        }

        return dataToTree[0];
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

/*******************************************************************************************/
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        /*
        将所有节点及空子节点放入result之后，再将result之后的多余的null删除;
        使用队列实现逐行从左到右遍历二叉树;
        to_string(),stoi()分别是将其他类型转换为string、int类型的函数
        一个小问题：将string的"+="换为push_back(char c)或append(string s)时，消耗内存将减少至原来的十分之一"
        */
        if(!root)  return "[null]";
        queue<TreeNode*> q;
        string result = "[";
        q.push(root);
        while(!q.empty()){
            if(q.front()){
                result.append(to_string(q.front()->val));
                result.push_back(',');
                q.push(q.front()->left);
                q.push(q.front()->right);
            }else{
                result.append("null,");
            }
            q.pop();
        }

        int endOfResult = result.size() - 1;
        while(result[endOfResult] < '0' || result[endOfResult] > '9'){
            result.pop_back();
            --endOfResult;
        }
        result.push_back(']');

        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "[null]")  return NULL;
        /*
        整体优化：使用一个队列，将所有已创建的节点放入其中；再创建一个字符串指针，用于标示节点创建进度；
        通过读取字符串创建新节点之后，随机创建其左右两个节点；当字符串指针到达末尾时，表示所有节点左右子树都已创建完，
        则弹出队列中所有叶节点即可
        */
        int dataptr = 0;  //字符串下标
        TreeNode* head = NULL;
        while(data[dataptr] == ' ')  ++dataptr;
        if(data[dataptr] == '[')  ++dataptr;

        int sizeOfData = data.size();
        queue<TreeNode*> dataQueue;

        while(dataptr < sizeOfData && data[dataptr] != ']'){
            if(dataQueue.empty()){
                TreeNode* pTreeNode = readNumber(data, dataptr, sizeOfData);
                dataQueue.push(pTreeNode);
                head = pTreeNode;
            }
            
            if(!dataQueue.front()){
                dataQueue.pop();
                continue;
            }
            //设定左右节点
            if(data[dataptr] != ']'){
                ++dataptr;
                dataQueue.front()->left = readNumber(data, dataptr, sizeOfData);
                dataQueue.push(dataQueue.front()->left);
            }
            if(data[dataptr] != ']'){
                ++dataptr;
                dataQueue.front()->right = readNumber(data, dataptr, sizeOfData);
                dataQueue.push(dataQueue.front()->right);
            }
            dataQueue.pop();
        }

        while(!dataQueue.empty())  dataQueue.pop();

        return head;
    }

    TreeNode* readNumber(string& data, int &ptr, int& sizeOfData){
        string temp = "";
        TreeNode* pTreeNode = NULL;
        while(ptr < sizeOfData && data[ptr] != ','){
            if(data[ptr] == ']')  break;
            temp += data[ptr];
            ++ptr;
        }
        if(temp != "null")  pTreeNode = new TreeNode(stoi(temp));
        return pTreeNode;
    }
};